All Questions
28 questions
1vote
0answers
104views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem, in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 11.6k
2votes
0answers
123views
Finding Hamilton cycles in random graphs
For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)? If this is an open problem, I will also accept an empirically ...
- 2,762
4votes
0answers
92views
Complexity of Encoding a Matroid Flow Problem in a Matrix
Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
- 696
2votes
0answers
54views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
- 6,952
3votes
0answers
147views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete: Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$? The reference provide was to the textbook “Computers and ...
- 625
5votes
2answers
296views
Log space algorithms for modular decomposition tree
Can we have log space algorithms for modular decomposition tree (see definition) for any graph? If not, can we have log space algorithms for modular decomposition tree for any particular graph class? ...
- 185
0votes
1answer
634views
Paritioning a graph into clique and independent set
I am interested in the complexity of the following problems: Input: an undirected graph $G = \langle V, E \rangle$ Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $...
- 221
8votes
1answer
402views
Complexity of "destroying" the graph's minimum spanning tree weight
Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$. Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\...
- 9,548
5votes
0answers
247views
Maximizing the number of selected edges with opposing requirements
Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...
9votes
0answers
564views
Is it possible to solve perfect matching in linear time
As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft. Is it possible to solve perfect matching problem in linear time for given $...
- 99
17votes
4answers
2kviews
Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs
I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs. I've seen the question regarding the other way around here “Directed” ...
- 9,548
43votes
3answers
3kviews
Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem
The Graph Isomorphism problem (GI) is arguably the best known candidate for an NP-intermediate problem. The best known algorithm is sub-exponential algorithm with run-time $2^{O(\sqrt{n \log n})}$. ...
4votes
1answer
1kviews
Path coloring in general graphs
Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors. We know that coloring a set of paths ...
- 1,601
17votes
4answers
659views
Hard Problems for higher genus graphs
Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple : Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs ...
- 10.6k
6votes
2answers
241views
Vertex subset of maximum size
I was wondering if this problem has a name and/or it has been already studied. Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ : Does ...
- 61
